Memory caches include partially associative caches and fully associative caches. In set-associative caches, memory is organized into a plurality of sets of N entries, or cachelines, where N is typically between 1 and 8. Each set of cachelines is reserved for a range of addresses or tags. New data is written over previously cached data in a set to which the new address maps. Set associative caches are also referred to as N-way associative caches. In a fully-associative cache, a new block of data can be written over previously cached data in any cacheline.
Cache replacement policies are used to select previously-cached data to be overwritten by new data. Cache replacement policies include least recently used (LRU) and least frequently used (LFU).
Caching is used in video processing, including motion estimation. Motion estimation is an inter-frame predictive coding process to reduce temporal redundancy in video sequences. In motion estimation, a reference video frame is searched for one or more macroblocks of pixels that are similar to a current macroblock of a video frame to be encoded. Similarity tests include a Sum-of-Absolute-Distortions (SAD).
When a similar macroblock is found in the reference frame, the current macroblock is encoded with a pointer and a matrix. The pointer or motion vector indicates a relative coordination between the current macroblock and the reference macroblock. A residual matrix identifies differences between pixels of the current macroblock and reference macroblock. Motion estimation processes include a Three-Step Search, a Four-Step Search, a Diamond Search, and a Modified Log Search.
Relatively high quality video may have 1920×1080 pixels per frame, at 30 frames per second. A macroblock may be as small as 4×4 pixels, and may be encoded with respect to up to sixteen reference macroblocks, within up to eight reference frames. Due to the relatively great amounts of data to be retrieved, cache replacement policies are important in video processing.
In the drawings, the leftmost digit(s) of a reference number identifies the drawing in which the reference number first appears.